package com.atguigui.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * 655.输出二叉树
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/8/22 10:10
 */
public class P655PrintBinaryTree {
    public static void main(String[] args) {
        Solution solution = new P655PrintBinaryTree().new Solution();
        // TO TEST
    }

    class Solution {
        public List<List<String>> printTree(TreeNode root) {
            //计算高度、矩阵
            int height = calDepth(root);
            int m = height + 1;
            int n = (1 << (height + 1)) - 1;

            //初始化矩阵
            List<List<String>> res = new ArrayList<List<String>>();
            for (int i = 0; i < m; i++) {
                List<String> row = new ArrayList<String>();
                for (int j = 0; j < n; j++) {
                    row.add("");
                }
                res.add(row);
            }


            Queue<Tuple> queue = new ArrayDeque<Tuple>();
            //root初始节点应该放在矩阵中的默认位置
            queue.offer(new Tuple(root, 0, (n - 1) / 2));
            while (!queue.isEmpty()) {
                Tuple t = queue.poll();
                TreeNode node = t.node;
                //r为矩阵的行数，c为矩阵行中的第几列
                int r = t.r, c = t.c;
                res.get(r).set(c, Integer.toString(node.val));
                if (node.left != null) {
                    //从中间往左便宜
                    queue.offer(new Tuple(node.left, r + 1, c - (1 << (height - r - 1))));
                }
                if (node.right != null) {
                    //从中间往右便宜
                    queue.offer(new Tuple(node.right, r + 1, c + (1 << (height - r - 1))));
                }
            }
            return res;
        }

        /**
         * 找出树最深深度
         *
         * @param root
         * @return
         */
        private int calDepth(TreeNode root) {
            int res = -1;
            Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int len = queue.size();
                res++;
                //遍历所有节点
                while (len > 0) {
                    len--;
                    TreeNode t = queue.poll();
                    if (t.left != null) {
                        queue.offer(t.left);
                    }
                    if (t.right != null) {
                        queue.offer(t.right);
                    }
                }
            }
            return res;
        }


        /**
         * 实体类维护当前节点在矩阵中存放的位置
         */
        class Tuple {
            TreeNode node;
            //矩阵中的位置
            int r;
            int c;

            public Tuple(TreeNode node, int r, int c) {
                this.node = node;
                this.r = r;
                this.c = c;
            }
        }
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
